package com.easy.leetcode.stack;

import java.util.HashMap;
import java.util.Map;
import java.util.Stack;

/**
 * @ClassName NextGreaterElement496
 * @Description 496. 下一个更大元素 I
 * 思路： 单调栈
 * 栈中的元素是依次减小，如果找到一个值大于栈顶元素，那么这个元素就是第一个比栈顶元素大的值。
 * 取出并记录该元素对应的第一个比它大的值。
 * 循环以上操作
 * @Author zheng
 * @Date 2021/9/7 20:04
 * @Version 1.0
 **/
public class NextGreaterElement496 {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        //求每一个元素右边第一个比当前元素大的元素
        Stack<Integer> stack = new Stack();
        Map<Integer, Integer> res = new HashMap<>();
        for (int i = 0; i < nums2.length; i++) {
            while (!stack.isEmpty() && stack.peek() < nums2[i]) {
                res.put(stack.pop(), nums2[i]);
            }
            stack.push(nums2[i]);
        }
        while (!stack.isEmpty()) {
            res.put(stack.pop(), -1);
        }
        for (int i = 0; i < nums1.length; i++) {
            nums1[i] = res.get(nums1[i]);
        }
        return nums1;
    }
}
